public class Solution4 {
    public int numDecodings(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        int[] dp = new int[n];

        // 初始化
        if(s[0] != '0') {
            dp[0] = 1;
        }else {
            return 0;
        }

        if(n == 1) {
            return dp[0];
        }

        if(s[1] != '0' && s[0] != 0) {
            dp[1] += 1;
        }
        int t = (s[0] - '0') * 10 + s[1] - '0';
        if(t >= 10 && t <= 26) {
            dp[1] += 1;
        }

        // 填表
        for(int i = 2; i < n; i++) {
            if(s[i] != '0') {
                dp[i] += dp[i - 1];
            }
            int tt = (s[i - 1] - '0') * 10 + s[i] - '0';
            if(tt >= 10 && tt <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n - 1];
    }

    public int numDecodings1(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        int[] dp = new int[n + 1];

        // 初始化
        dp[0] = 1; // 保证后续填表是正确的
        if(s[1 - 1] != '0') {
            dp[1] = 1;
        }

        // 填表
        for(int i = 2; i <= n; i++) {
            if(s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            int tt = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if(tt >= 10 && tt <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}
